/**
 * 
 */
package tree.passed2;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author xyyi
 *
 */
public class BinaryTreeZigzagLevelOrderTraversal {

	/**
	Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

	For example:
	Given binary tree {3,9,20,#,#,15,7},
	 */
	public ArrayList<ArrayList<Integer>> zigzagLevelOrder2Stack(TreeNode root) {
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		if (root == null)
			return result;
		Stack<TreeNode> currentLevel = new Stack<TreeNode>();
		Stack<TreeNode> nextLevel = new Stack<TreeNode>();
		ArrayList<Integer> levelList = new ArrayList<Integer>();
		currentLevel.push(root);
		boolean leftToRight = true;
		while (!currentLevel.isEmpty()) {
			TreeNode node = currentLevel.pop();

			levelList.add(node.val);
			if (leftToRight) {
				if (node.left != null)
					nextLevel.push(node.left);
				if (node.right != null)
					nextLevel.push(node.right);
			} else {
				if (node.right != null)
					nextLevel.push(node.right);
				if (node.left != null)
					nextLevel.push(node.left);
			}

			if (currentLevel.isEmpty()) {
				result.add(new ArrayList<Integer>(levelList));
				levelList.clear();
				leftToRight = !leftToRight;
				Stack<TreeNode> temp = currentLevel;
				currentLevel = nextLevel;
				nextLevel = temp;
			}
		}

		return result;
	}

	public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
		// Start typing your Java solution below
		// DO NOT write main() function
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		if (root == null)
			return result;
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(root);
		queue.offer(null);
		ArrayList<Integer> buffer = new ArrayList<Integer>();
		boolean needReverse = false;
		while (!queue.isEmpty()) {
			TreeNode node = queue.poll();
			if (node != null) {
				buffer.add(node.val);
				if (node.left != null)
					queue.offer(node.left);
				if (node.right != null)
					queue.offer(node.right);
			} else {
				if (needReverse) {
					Collections.reverse(buffer);
				}
				result.add(new ArrayList<Integer>(buffer));
				needReverse = !needReverse;
				buffer.clear();
				if (!queue.isEmpty()) {
					queue.add(null);
				}
			}
		}

		return result;
	}

	/**
	 * Definition for binary tree
	 */
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	/**
	 * 
	 */
	public BinaryTreeZigzagLevelOrderTraversal() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
